這題目最一開始要做的事情就是，搞清楚什麼是bipartite？

一張圖具有bipartite的性質的話，代表可以分成bi個party，然後裡面的元素都可以跟對面party連緊緊(隨意胡謅)。

可以把圖裡的node分成兩個獨立集合，獨立集合也就是說兩個交集沒結果，然後可以全連接這樣。
　
　
　

思路：

我只能感受到...邊要偶數條邊，還有圖裡面，一定會有複數個點，他們連到的點是相同的。

但還是沒想法。

吸收知識時間

這題可以把她等價轉換成塗色問題，bipartite還有一個性質，而且是解問題的關鍵：連線只在不同集合之間，同個集合的點是不會有連線的，所以可以在BFS中，把該點連接出去的鄰居都塗上不同顏色，只要沒有衝突，就繼續塗色，直到把所有點分成不同顏色為止。
　
　
　

程式碼

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n); // [0, 1, -1] = [uncolor, A, B] = [unvisited, 已分組, 已分組]
        
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (color[i]) continue;
            
            color[i] = 1;
            q.push(i);
            while(!q.empty()) {
                int curr_node = q.front();
                for (int neighbor: graph[curr_node]) {
                    if (!color[neighbor]) {
                        color[neighbor] = -color[curr_node];
                        q.push(neighbor);
                    }
                    else if (color[neighbor] == color[curr_node])
                        return false;
                }
                q.pop();
            }
        }
        return true;
  }
};

大神

for (q.push(i); !q.empty(); q.pop()) { 
    ... 
}

我從來..沒試過把queue跟for結合，好厲害！

參考：
https://leetcode.com/problems/is-graph-bipartite/discuss/409594/Clean-C%2B%2B-BFS-with-explanation-and-comments
https://www.youtube.com/watch?v=oDqjPvD54Ss